﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using Common;

namespace Satire.Lexer
{
    // BNF for a regular expression
    //  Expr    --> Term ('|' Term)*
    //  Term    --> Fact Fact*
    //  Fact    --> ele '*' | ele '?' | ele '+' | ele | '(' Expr ')'
    //  ele     --> char | macro  


    //  char    --> '[' ranges ']' | '['~' ranges ']' | c
    //  ranges  --> range (range)*
    //  range   --> c | c '-' c 
    //  c       --> c1 | '\' c2 | '\' 'x' c3 c3

    // Terminals
    //  c1 - all chars except '|' '*' '?' '+' '(' ')' '.' '{' '}' '-' '\' 
    //  c2 - all chars except 'x'
    //  c3 - [0-9A-Za-z]


    public class Token 
    {
        public enum TokenType { ERROR, EOF, LB, RB, CLOSP, OR, CLOS, OPT, MACRO, CHARS }
        public Token(TokenType tt, int pos) { _tt = tt; _pos = pos; }
        public TokenType Type { get { return _tt; } }
        public int Pos { get { return _pos; } }

        private TokenType _tt;
        private int _pos;
    }
    public class TokenError : Token
    {
        public TokenError(string message, int pos) : base(TokenType.ERROR, pos)
        {
            _message = message;
        }
        public string Message { get { return _message; } }

        private string _message;
    }
    public class TokenMacro : Token
    {
        public TokenMacro(string name, int pos)
            : base(TokenType.MACRO, pos)
        {
            _name = name;
        }
        public string name { get { return _name; } }

        private string _name;
    }
    public class TokenChars : Token
    {
        public TokenChars(int[] chars, int pos)
            : base(TokenType.CHARS, pos)
        {
            _chars = chars;
        }
        public int[] Chars { get { return _chars; } }

        private int[] _chars;
    }

    public class Scanner
    {
        public Scanner() { }
        public const int MaxChar = 0xFF;
        public void Initialize(string re)
        {
            _pos = 0;
            _re = re;
            if (re.Length == 0)
            {
                _token = new Token(Token.TokenType.EOF, _pos);
            }
            else
            {
                _token = RawGetToken();
            }
        }
        public Token GetToken()
        {
            if (_token.Type == Token.TokenType.ERROR || _token.Type == Token.TokenType.EOF)
            {
                return _token;
            }
            Token saveToken = _token;
            if (_pos >= _re.Length) { _token = new Token(Token.TokenType.EOF, _pos); return saveToken; }
            _token = RawGetToken();
            return saveToken;
        }
        public Token PeekToken()
        {
            return _token;
        }
        private Token RawGetToken()
        {
 
            switch (_re[_pos])
            {
                case '(': _pos++; return new Token(Token.TokenType.LB, _pos);
                case ')': _pos++; return new Token(Token.TokenType.RB, _pos);
                case '+': _pos++; return new Token(Token.TokenType.CLOSP, _pos);
                case '|': _pos++; return new Token(Token.TokenType.OR, _pos);
                case '*': _pos++; return new Token(Token.TokenType.CLOS, _pos);
                case '?': _pos++; return new Token(Token.TokenType.OPT, _pos);
                case '{':
                    string tempName = ParseMacro(ref _pos, _re);
                    if (tempName == null) { return new TokenError("LEXER: Invalid Macro", _pos); }
                    return new TokenMacro(tempName, _pos);
                default: 
                    int[] tempChars = ParseChar(ref _pos, _re);
                    if (tempChars == null) { return new TokenError("LEXER: Invalid Character Set", _pos); }
                    return new TokenChars(tempChars, _pos);
            }
        }

        public enum OperatorType { LB, RB, CLOSP, OR, CLOS, OPT }
        private int[] ParseChar(ref int i, string re)
        {
            int[] ret = null;
            switch (re[i])
            {
                case '[':
                    // check for ~ 
                    i++;
                    if (i >= re.Length) { return null; }
                    bool neg = false;
                    if (re[i] == '~') { neg = true; i++; if (i >= re.Length) { return null; } }
                    _workSet.SetAll(false);
                    while (re[i] != ']')
                    {
                        int temp1 = GetChar(ref i, re);
                        int temp2 = temp1;
                        if (temp1 == -1 || i >= re.Length) { return null; }
                        if (re[i] == '-')
                        {
                            i++;
                            if (i >= re.Length) { return null; }
                            temp2 = GetChar(ref i, re);
                            if (temp2 == -1 || i >= re.Length) { return null; }
                        }
                        for (int j = temp1; j <= temp2; j++)
                        {
                            _workSet[j] = true;
                        }
                    }
                    i++;
                    if (neg) { _workSet.Not(); }
                    ret = _sau.ToStackedArray(_workSet);
                    break;
                case '.':
                    _workSet.SetAll(true);
                    ret = _sau.ToStackedArray(_workSet);
                    i++;
                    break;
                default:
                    int temp = GetChar(ref i, re);
                    if (i == -1) { return null; }
                    ret = new int[1];
                    ret[0] = temp;
                    break;
            }
            return ret;
        }
        private string ParseMacro(ref int i, string re)
        {
            i++;
            string name = "";
            while (i < re.Length && re[i] != '}')
            {
                if (!char.IsLetterOrDigit(re[i]))
                {
                    return null;
                }
                name += re[i];
                i++;
            }
            if (i == re.Length)
            {
                return null;
            }
            else
            {
                i++;
            }
            return name;
        }
        private int GetChar(ref int i, string re)
        {
            int ret = -1;
            switch (re[i])
            {
                case '\\':
                    i++;
                    if (i < re.Length)
                    {
                        ret = escape(re[i]);
                        i++;
                    }
                    break;
                default:
                    ret = re[i];
                    i++;
                    break;
            }
            return ret;
        }
        private static int escape(int c)
        {
	        switch(c) 
            {
		        case 'a': return 7;
		        case 'b': return '\b';
	        	case 'f': return '\f';
		        case 'n': return '\n';
		        case 'r': return '\r';
		        case 't': return '\t';
		        case 'v': return '\v';
		        default: return c;
	        }
        }
        private string _re;
        private int _pos;
        private BitArray _workSet = new BitArray(Scanner.MaxChar);
        private StackArrayUtility _sau = new StackArrayUtility(Scanner.MaxChar);
        private Token _token;
    }

    public class ParserError
    {
        public ParserError(int pos, string message) 
        {
            _pos = pos;
            _message = message;
        }
        public int Pos { get { return _pos; } }
        public string Message { get { return _message; } }

        private int _pos;
        private string _message;
    }
  
    abstract public class Parser 
    {
        public bool Parse(string re)
        {
            _scanner.Initialize(re);
            return _parse_expr();
        }

        public ParserError Error { get { return _error; } }

        abstract protected void EventMacro(int pos, string name);
        abstract protected void EventConcat(int pos);
        abstract protected void EventOr(int pos);
        abstract protected void EventClos(int pos);
        abstract protected void EventClosp(int pos);
        abstract protected void EventOpt(int pos);
        abstract protected void EventChars(int pos, int[] chars);

        private bool _parse_expr()
        {
            if (!_parse_term())
            {
                return false;
            }
            while (_scanner.GetToken().Type == Token.TokenType.OR)
            {
                if (!_parse_term())
                {
                    return false;
                }
                EventOr(_scanner.PeekToken().Pos);
             }
            if (_scanner.PeekToken().Type != Token.TokenType.EOF)
            {
                _error = new ParserError(_scanner.PeekToken().Pos, "PARSER: Extra characters at end of expression");
                return false;
            }
            return true;
        }
        private bool _parse_term()
        {
            if (!_parse_fact())
            {
                return false;
            }
            while (_scanner.PeekToken().Type != Token.TokenType.EOF && 
                _scanner.PeekToken().Type != Token.TokenType.OR &&
                _scanner.PeekToken().Type != Token.TokenType.RB) 
            {
                if (!_parse_fact())
                {
                    return false;
                }
                EventConcat(_scanner.PeekToken().Pos);
            }
            return true;
        }
        private bool _parse_fact()
        {
            if (_scanner.PeekToken().Type == Token.TokenType.LB)
            {
                _scanner.GetToken();
                if (!_parse_expr())
                {
                    return false;
                }
                if (_scanner.PeekToken().Type != Token.TokenType.RB)
                {
                    _error = new ParserError(_scanner.PeekToken().Pos, "PARSER: ) expected");
                    return false;
                }
                _scanner.GetToken();
                return true;
            }
           
            if (!_parse_ele())
            {
                return false;
            }
            if (_scanner.PeekToken().Type == Token.TokenType.CLOS)
            {
                EventClos(_scanner.PeekToken().Pos);
                _scanner.GetToken();
                return true;
            }
            if (_scanner.PeekToken().Type == Token.TokenType.OPT)
            {
                EventOpt(_scanner.PeekToken().Pos);
                _scanner.GetToken();
                return true;
            }
            if (_scanner.PeekToken().Type == Token.TokenType.CLOSP)
            {
                EventClosp(_scanner.PeekToken().Pos);
                _scanner.GetToken();
                return true;
            }
            return true;
        }
        private bool _parse_ele()
        {
            Token tkn = _scanner.GetToken();
            if (tkn.Type == Token.TokenType.MACRO)
            {
                TokenMacro tm = tkn as TokenMacro;
                EventMacro(_scanner.PeekToken().Pos, tm.name);
                return true;
            }
            if (tkn.Type == Token.TokenType.CHARS)
            {
                TokenChars tc = tkn as TokenChars;
                EventChars(_scanner.PeekToken().Pos, tc.Chars);
                return true;
            }
            _error = new ParserError(_scanner.PeekToken().Pos, "PARSE: Macro, Character set or Character expected");
            return false;
        }
        private Scanner _scanner = new Scanner();
        private ParserError _error = null;

    }
}
